You are given a 0-indexed integer array nums and an integer k.
You are initially standing at index 0. In one move, you can jump at most k steps forward without going outside the boundaries of the array. That is, you can jump from index i to any index in the range [i + 1, min(n - 1, i + k)] inclusive.
You want to reach the last index of the array (index n - 1). Your score is the sum of all nums[j] for each index j you visited in the array.
Return the maximum score you can get.
Example 1:
Input: nums = [1,-1,-2,4,-7,3], k = 2 Output: 7 Explanation: You can choose your jumps forming the subsequence [1,-1,4,3] (underlined above). The sum is 7.
Example 2:
Input: nums = [10,-5,-2,4,0,3], k = 3 Output: 17 Explanation: You can choose your jumps forming the subsequence [10,4,3] (underlined above). The sum is 17.
Example 3:
Input: nums = [1,-5,-20,4,-1,3,-6,-3], k = 2 Output: 0
Constraints:
-
1 <= nums.length, k <= 105 -104 <= nums[i] <= 104
Average Rating: 4.08 (25 votes)
Solution
Overview
You probably can guess from the problem title, this is the sixth problem in the series of Jump Game problems. Those problems are similar, but have considerable differences, making their solutions quite different.
In this problem, for each move, we are allowed to advance k steps, and our target is to maximize the scores we collect.
One example:
Below, five approaches are introduced.
Generally, we recommend Approach 1: Dynamic Programming + Deque and Approach 4: Dynamic Programming + Deque (Compressed) since they have the best performance.
Also, because it is a medium level problem, we allow some relevant slower approaches: Approach 2: Dynamic Programming + Priority Queue and Approach 3: Segment Tree.
Note that Approach 4: Dynamic Programming + Deque (Compressed) and Approach 5: Dynamic Programming + Priority Queue (Compressed) are the state compressed version of Approach 1 and Approach 2.
Approach 1: Dynamic Programming + Deque
Intuition
Note: This approach is a little bit beyond the medium level question, so if you are struggling to understand this, you should at least finish the DP part, and then feel free to jump to Approach 2 , which is easier but has a slower performance.
However, it is still strongly recommended to understand this whole approach since it is not that hard.
In this part, we will explain how to think of this approach step by step.
If you are only interested in the pure algorithm, you can jump to the algorithm part.
For the Jump Game series questions, dynamic programming is our old friend. It's natural to try DP first.
To implement DP, we need a dp array. What should the DP array represent?
Since the problem ask us the max score we can get ending at the last index, how about letting dp[i] represent the max score we can get ending at index i?
Also, you can let
dp[i]represent the max score we can get starting at indexi. That is similar.
To have better naming, we rename dp to score. So, score[i] represents the max score we can get ending at index i.
For example:
OK. Let's dive deeper.
For a DP solution, basically, we need two things:
- The base case.
This is where our dp start. Usually, this means how to calculate dp[0]. In our case, score[0] = nums[0] since nums[0] is both our start and end. We only have one choice.
- The so-called transition equation.
That is to say, if we have already calculated score[0], score[1], ..., score[i-1], how can we calculate score[i]?
Since we can only advance k steps, to arrive nums[i], we must jump from one of nums[i-k], nums[i-k+1], ..., nums[i-1]. We only need to pick the one with maximum score.
For example, if we are calculating score[3] and k=3, we need to decide jump from index 0, 1, or 2:
OK, now we have a transition equation:
score[i] = max(score[i-k], ..., score[i-1]) + nums[i]
However, this equation needs O(k) to calculate score[i], which makes the overall complexity come to O(Nk)=109 in the worst case, given that N is the length of nums.
This complexity is too much and we need to improve it.
Somehow, this equation is similar to Sliding Window Maximum, which is a typical monotonic queue problem. We can use the same technique to make some improvements.
Note that when calculating maximum, we do not need all score[i-k], ..., score[i-1]; we just need some large values.
For example, if k == 3 and [score[i-3], score[i-2], score[i-1]] = [2, 4, 10], their maximum is score[i-1] = 10. In this case, when calculating following score[i] (and further score[i+1]), we do not need score[i-3] = 2 and score[i-2] = 4, since they are smaller than score[i-1] = 10.
The picture illustrates another example when calculating score[2]:
In this case, we maintain a deque as a monotonically decreasing queue. Since it is monotonically decreasing, the maximum value is always at the top of the queue.
In practice, since we store scores in score, we only need to store the index in the queue.
Also, remember to pop the index smaller than i-k out of the queue from the left.
Algorithm
Step 1: Initialize a dp array score, where score[i] represents the max score starting at nums[0] and ending at nums[i].
Step 2: Initialize a deque array dq storing indexes of nums such that the corresponding values are monotonically decreasing.
Step 3: Iterate over nums. For each element nums[i]:
- Pop all the indexes smaller than
i-kout ofdqfrom left. - Update
score[i]toscore[dq.peekFirst()] + nums[i]. - If the corresponding score of the rightmost index in
dq(i.e.,score[dq.peekLast()]) is smaller thanscore[i], pop it from the right to make corresponding values monotonically decreasing. Repeat. - Push
iinto the right ofdq.
Step 4: Return the last element of score.
Challenge: Can you implement the code yourself without seeing our implementations?
Implementation
Complexity Analysis
Let N be the length of nums.
-
Time Complexity: O(N), since we need to iterate
nums, and push and pop each element into the deque at most once. -
Space Complexity: O(N), since we need O(N) space to store our dp array and O(k) to store
dq.
Approach 2: Dynamic Programming + Priority Queue
Intuition
In Approach 1, we got the following transition equation for Dynamic Programming:
score[i] = max(score[i-k], ..., score[i-1]) + nums[i]
If you are not familiar with the monotonic queue technique mentioned in Approach 1, and still want to find out the maximum quickly, Priority Queue (Heap) is for you. Heap maintain and return the max value in log time.
If we found that the index of the maximum score is less than i-k, just pop out and get the next maximum score.
Algorithm
Step 1: Initialize a dp array score, where score[i] represents the max score starting at nums[0] and ending at nums[i].
Step 2: Initialize a max-heap priority_queue.
Step 3: Iterate over nums. For each element nums[i]:
- If the index of top of
priority_queueis less thani-k, pop the top. Repeat. - Update
score[i]to the sum of corresponding score of the index of top ofpriority_queueandnums[i](i.e.,score[priorityQueue.peek()[1]] + nums[i]). - Push pair
(score[i], i)intopriority_queue.
Step 4: Return the last element of score.
Challenge: Can you implement the code yourself without seeing our implementations?
Implementation
Complexity Analysis
Let N be the length of nums.
-
Time Complexity: O(NlogN), since we need to iterate
nums, and push and pop each element into the deque at most once, and for each push and pop, it costs O(logN) in the worst case. -
Space Complexity: O(N), since we need O(N) space to store our dp array and O(N) to store
priority_queue.
Approach 3: Segment Tree
Intuition
In Approach 1, we got the following transition equation for Dynamic Programming:
score[i] = max(score[i-k], ..., score[i-1]) + nums[i]
There is also another way to find out the interval maximum in log time: Segment Tree.
Since we already have some great explanations on Segment Tree, here we will not provide a detailed explanation of implementation. You can find some comprehensive tutorials on Recursive Approach to Segment Trees or Range Sum Query - Mutable.
Now, we will have a quick review of the segment tree and then explain how we can use it to tackle our problem.
As we know, the segment tree is a data structure used for storing information about intervals. Given that N is the size of the tree, this data structure allows us to query and to update the information about a certain interval in O(log(N)) time.
Take the segment tree for querying interval max for an example:
Usually, we store the tree in an array. We need twice the size of the original array to store the segment tree.
Here, we leave the index 0 unused for the convenience of indexing. You can also choose to use it by shifting the whole tree to left by one unit. In our approach, the left and right children of node i are 2*i and 2*i + 1 respectively.
Given that n is the size of the original array, from the node n to node 2*n - 1, we store the original array itself. For other nodes, we store the value of node i as the sum of node 2*i and node 2*i + 1.
The segment tree allows us to query the max of a certain interval and to update the values of elements. It should be able to process both actions in O(log(N)) time. Let's see some examples.
Updating Value
For update, what we do is simple. Just update the value from the leaf to the root. For instance:
Querying Sum
For query, the case is a bit complicated. Generally speaking, we are dividing the target interval into a few pre-calculated segments to reduced run time. For example:
OK. Now back to our problem. How can we use the segment tree?
For each element nums[i], we need to query max(score[i-k], ..., score[i-1]), and then update the value of index i in Segment Tree to that maximum plus nums[i]. Both actions can be implemented in log time.
Algorithm
Step 1: Implement the Segment Tree. Since the tree is initialized to all zeros, only update and query need to be implemented.
Step 2: Iterate over nums. For each element nums[i]:
querythe maximum from indexi-kto indexi.updatevalue of indexito that maximum plusnums[i].
Step 3: Return the last element of the segment tree.
Challenge: Can you implement the code yourself without seeing our implementations?
Implementation
Complexity Analysis
Let N be the length of nums.
-
Time Complexity: O(NlogN), since we need to iterate
nums, and for each element we need to perform thequeryandupdateonce, which costs O(logN) in the worst case. -
Space Complexity: O(N), since we need O(N) space to store our segment tree.
Approach 4: Dynamic Programming + Deque (Compressed)
Intuition
Note that in Approach 1, when calculating score[i], we do not need all values from score[0] to score[i-1]; we only need part of values from score[i-k] to score[i-1]. We can drop the previous values to save memory.
But how? Note that we have a deque array dq, we can save score[i] when saving index i, and drop the whole score array. That is to say, we save a pair (i, score[i]) in the deque. The length of dq is at most O(k), so the space complexity is down to O(k).
Algorithm
Step 1: Initialize an integer score.
Step 2: Initialize a deque array dq.
Step 3: Iterate over nums. For each element nums[i]:
- Pop all the indexes smaller than
i-kout ofdqfrom left. - Update
scoretodq.peekFirst()[1] + nums[i]. - If the corresponding score of the rightmost index in
dq(i.e.,dq.peekLast()[1]) is smaller thanscore, pop it from the right to make corresponding values monotonically decreasing. Repeat. - Push
(i, score)into the right ofdq.
Step 4: Return score.
Challenge: Can you implement the code yourself without seeing our implementations?
Implementation
Complexity Analysis
Let N be the length of nums.
-
Time Complexity: O(N), since we need to iterate
nums, and push and pop each element into the deque at most once. -
Space Complexity: O(k), since we need O(k) to store
dq.
Approach 5: Dynamic Programming + Priority Queue (Compressed)
Intuition
Similar to Approach 4, when calculating score[i], we do not need all values from score[0] to score[i-1]; we only need values from score[i-k] to score[i-1]. We can drop the previous values to save memory.
Since we already save the (score[i], i) pair in our Priority Queue, we can directly drop the score array.
However, the length of our Priority Queue is O(N) in the worst case, given that N is the length of nums. That is to say, we can not decrease the big-O space complexity. Nevertheless, we still decrease memory usage by half by dropping the score array.
Algorithm
Step 1: Initialize an integer score.
Step 2: Initialize a max-heap priority_queue.
Step 3: Iterate over nums. For each element nums[i]:
- If the index of top of
priority_queueis less thani-k, pop the top. Repeat. - Update
scoreto the sum of corresponding score of the index of top ofpriority_queueandnums[i](i.e.,priorityQueue.peek()[0] + nums[i]). - Push pair
(score, i)intopriority_queue.
Step 4: Return score.
Challenge: Can you implement the code yourself without seeing our implementations?
Implementation
Complexity Analysis
Let N be the length of nums.
-
Time Complexity: O(NlogN), since we need to iterate
nums, and push and pop each element into the deque at most once, and for each push and pop, it costs O(logN) in the worst case. -
Space Complexity: O(N), since we need O(N) to store
priority_queue.
December 20, 2020 10:32 PM
This should be a hard level question
December 20, 2020 10:17 AM
Thanks for the detailed explanation 🙂
This seems a hard questions as the priority queue step in answer 2 can be used to solve sliding window maximum (a LC hard question).
This problem is kind of an extension to the max sliding window problem, which is labelled as a hard, so this one definitely deserves a hard.
December 21, 2020 4:05 AM
Good problem and good explanation! One thing though: It's not guaranteed that k is always less than the length of nums so getting rid of score array will not necessarily improve the space complexity.
December 20, 2020 9:51 AM
Great explanation!
My brain stopped after I came up with a O(n^2) dp solution and then it exceeds time limit, and I am not able to get my brain to restart to comprehend these sliding window and priority queue methods after I looked at the solution, sad.
Last Edit: May 5, 2021 2:14 AM
C++ Solution 1: line 11 while loop can also be a for loop.
if (!dq.empty() && dq.front() < i-k) {
Thanks for the solution.
Another simple Sliding window solution with O(1) space & O(n) runtime
https://leetcode.com/problems/jump-game-vi/discuss/981340/Explained%3A-Simple-Sliding-window-solution-with-O(1)-space-and-O(n)-runtime
Last Edit: December 20, 2020 11:46 PM
Thanks for nice explanation, leetcode articles getting better and better now a days. Need one clarification on Approach 5 Time Complexity. How is time complexity O(NlogN)? I thought priorityQueue.remove();itself would be O(N).
You don't have any submissions yet.
xxxxxxxxxxclass Solution {public: int maxResult(vector<int>& nums, int k) { }};